"""
分治法和动态规划（DP）是算法设计中两种重要的思想，均通过分解问题来高效求解，但核心思路和适用场景有显著差异。以下是具体定义、实例及对比：

分治法（Divide and Conquer）
定义
分治法是一种将复杂问题分解为规模更小的同类子问题，递归求解子问题后，将子问题的解合并为原问题解的算法思想。

核心步骤：
1: 分解（Divide）：将原问题拆分为多个规模较小、结构与原问题一致的子问题。
2: 求解（Conquer）：递归求解子问题（若子问题规模足够小，则直接求解）。
3:合并（Combine）：将子问题的解合并，得到原问题的解。

适用场景：子问题相互独立（无重叠），且合并步骤可高效实现。
举例：归并排序（Merge Sort）

问题：对一个无序数组进行排序。
分治思路：
分解：将数组从中间拆分为两个子数组，递归拆分直到子数组长度为 1（单个元素天然有序）。
求解：子数组长度为 1 时直接返回。
合并：将两个有序子数组合并为一个更大的有序数组（通过双指针比较元素大小，依次放入结果数组）。

def merge_sort(arr):
    # 终止条件：子数组长度为1时直接返回
    if len(arr) <= 1:
        return arr
    # 分解：拆分为左右两个子数组
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # 合并：将两个有序子数组合并
    return merge(left, right)

def merge(left, right):
    res = []
    i = j = 0
    # 双指针合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    # 拼接剩余元素
    res.extend(left[i:])
    res.extend(right[j:])
    return res

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # 输出：[3, 9, 10, 27, 38, 43, 82]


动态规划（Dynamic Programming, DP）
定义
动态规划是一种通过存储子问题的解（避免重复计算）来高效求解具有重叠子问题和最优子结构的问题的思想。
核心概念：
重叠子问题：问题的子问题之间存在重复，可通过缓存（如 “DP 表”）存储已求解的子问题结果。
最优子结构：原问题的最优解包含子问题的最优解（可通过子问题的最优解推导原问题的最优解）。

核心步骤：
1：定义状态：用dp[i]或dp[i][j]表示子问题的解（明确i/j的含义）。
2：推导转移方程：建立子问题与原问题的关系（如dp[i] = f(dp[i-1], dp[i-2], ...)）。
3：初始化与边界条件：确定最小子问题的解（如dp[0]、dp[1]）。
4：计算顺序：按依赖关系从小到大计算 DP 表（避免子问题未求解时被引用）。

举例1：斐波那契数列（Fibonacci Sequence）
问题：求第n个斐波那契数（定义：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)）。
DP 思路：
重叠子问题：计算F(5)需F(4)和F(3)，计算F(4)需F(3)和F(2)，F(3)被重复计算。
用dp[i]存储第i个斐波那契数，转移方程为dp[i] = dp[i-1] + dp[i-2]。

def fibonacci(n):
    if n <= 1:
        return n
    # 定义DP表，存储子问题解
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1  # 初始化
    # 按顺序计算（从小到大）
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 转移方程
    return dp[n]

print(fibonacci(10))  # 输出：55

举例 2：最长公共子序列（LCS）
问题：给定两个字符串text1和text2，求它们最长公共子序列的长度（子序列不要求连续）。
DP 思路：
状态定义：dp[i][j]表示text1[0..i-1]与text2[0..j-1]的 LCS 长度。
转移方程：
若text1[i-1] == text2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1（当前字符加入 LCS）。
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取去掉一个字符后的最大 LCS）。

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    # 定义DP表，初始化为0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(longest_common_subsequence("abcde", "ace"))  # 输出：3（公共子序列为"ace"）



三、分治法与动态规划的核心区别
维度	            分治法	                动态规划
子问题关系	  子问题独立（无重叠）	        子问题重叠（需避免重复计算）
核心操作	      分解后合并子问题的解	        存储子问题解（DP表），通过转移方程推导
适用场景	      排序、二分查找、快速幂等	    最优路径、资源分配、序列匹配等
实现方式	      递归（为主）	            迭代（DP表）或记忆化递归

简言之，分治法通过 “拆分 - 求解 - 合并” 处理独立子问题，
动态规划通过 “缓存子问题解” 高效处理重叠子问题，二者均体现 “分而治之” 的思想，但优化方向不同。




"""